/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/generate-parentheses
   @Language: C++
   @Datetime: 19-05-30 14:35
   */

class Solution {
	void backtrack(int left, int right, vector<string> &vs, string &s){
		if(left==0 && right==0){
			vs.push_back(s);
			return;
		}
		if(left){
			s.push_back('(');
			backtrack(left-1,right,vs,s);
			s.pop_back();
		}
		if(left<right){
			s.push_back(')');
			backtrack(left,right-1,vs,s);
			s.pop_back();
		}
	}
public:
	vector<string> generateParenthesis(int n) {
		vector<string> vs;
		string s;
		backtrack(n,n,vs,s);
		return vs;
	}
};
